package leetcode1;

public class Day9 {

    public static void main(String[] args) {
        String s = "aa";
        String p = "*";
        //isMatch(s,p);
    }

    //44.通配符匹配
    public boolean isMatch(String s, String p) {
        s = "_" + s; p = "_" + p;
        int n=s.length(),m=p.length();
        boolean[][] dp = new boolean[n][m];
        dp[0][0]=true;
        for(int i=1;i<m;i++) {
            if(p.charAt(i) != '*') break;
            else dp[0][i]=true;
        }
        for(int i=1;i<n;i++) {
            for(int j=1;j<m;j++) {
                char ch = p.charAt(j);
                if(ch == '?') dp[i][j]=dp[i-1][j-1];//?
                else if(ch != '*') {//普通字符
                    if(ch == s.charAt(i)) dp[i][j]=dp[i-1][j-1];
                }
                else {
                    if(dp[i][j-1] || dp[i-1][j]) dp[i][j]=true;
                }
            }
        }
        return dp[n-1][m-1];
    }
}
